package com.leetcode;

import com.leetcode.common.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 143. 重排链表
 * 线性表
 * 利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表
 *
 * @author fy
 * @date 2022/4/11 20:55
 */
public class Solution143_1 {

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }
        int i = 0;
        int j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }

            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}
